{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Knight Probability in Chessboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: knightProbability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #骑士在棋盘上的概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个&nbsp;<code>n x n</code>&nbsp;的国际象棋棋盘上，一个骑士从单元格 <code>(row, column)</code>&nbsp;开始，并尝试进行 <code>k</code> 次移动。行和列是 <strong>从 0 开始</strong> 的，所以左上单元格是 <code>(0,0)</code> ，右下单元格是 <code>(n - 1, n - 1)</code> 。</p>\n",
    "\n",
    "<p>象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/knight.png\" style=\"height: 300px; width: 300px;\" /></p>\n",
    "\n",
    "<p>每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。</p>\n",
    "\n",
    "<p>骑士继续移动，直到它走了 <code>k</code> 步或离开了棋盘。</p>\n",
    "\n",
    "<p>返回 <em>骑士在棋盘停止移动后仍留在棋盘上的概率</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, k = 2, row = 0, column = 0\n",
    "<strong>输出:</strong> 0.0625\n",
    "<strong>解释:</strong> 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。\n",
    "在每一个位置上，也有两种移动可以让骑士留在棋盘上。\n",
    "骑士留在棋盘上的总概率是0.0625。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1, k = 0, row = 0, column = 0\n",
    "<strong>输出:</strong> 1.00000\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 25</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= row, column &lt;= n - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [knight-probability-in-chessboard](https://leetcode.cn/problems/knight-probability-in-chessboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [knight-probability-in-chessboard](https://leetcode.cn/problems/knight-probability-in-chessboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2\\n0\\n0', '1\\n0\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        g = [[0.0] * n for _ in range(n)]\n",
    "        t = [[0.0] * n for _ in range(n)]\n",
    "        g[row][column] = 1\n",
    "        p = 1 / 8\n",
    "        for _ in range(k):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    t[i][j] = 0.0\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    for nx,ny in [(x-2, y-1),(x-2, y+1),(x-1,y-2),(x-1,y+2),(x+2,y+1),(x+2,y-1),(x+1, y-2),(x+1,y+2)]:\n",
    "                        if 0 <= nx < n and 0 <= ny < n:\n",
    "                            t[nx][ny] += g[x][y] * p\n",
    "            t,g = g,t\n",
    "        return sum([sum(x) for x in g])\n",
    "\n",
    "s = Solution()\n",
    "s.knightProbability(3,2,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp=[[[1.0]*n for _ in range(n)] for _ in range(2)]\n",
    "        for r in range(1,k+1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dp[r&1][i][j]=0.0\n",
    "                    for di,dj in ((-2,-1),(-2,1),(2,-1),(2,1),(-1,-2),(-1,2),(1,-2),(1,2)):\n",
    "                        ni,nj=i+di,j+dj\n",
    "                        if 0<=ni<n and 0<=nj<n:\n",
    "                            dp[r&1][i][j]+=dp[(r-1)&1][ni][nj]/8\n",
    "        return dp[k&1][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        dp[row][column] = 1\n",
    "        ret = 1 \n",
    "        for _ in range(k):\n",
    "            tmp = [[0]*n for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if dp[i][j]:\n",
    "                        for l, r in [(i+1, j+2), (i-1, j+2), (i+2, j+1), (i+2, j-1), (i+1, j-2), (i-1, j-2), (i-2, j+1), (i-2, j-1)]:\n",
    "                            print(l, r)\n",
    "                            if 0 <= l < n and 0 <= r < n:\n",
    "                                tmp[l][r] += dp[i][j]*1/8\n",
    "                            else:\n",
    "                                ret -= dp[i][j]*1/8\n",
    "            # for t in tmp:\n",
    "            #     print(t)\n",
    "            # for t in dp:\n",
    "            #     print(t)\n",
    "            dp = tmp[:]\n",
    "            # for idx, t in enumerate(tmp):\n",
    "            #     dp[idx] = t[:]\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k==0:\n",
    "            return 1\n",
    "        import copy\n",
    "        ls=[[0 for j in range(n)] for i in range(n)]\n",
    "        lxy=[[[] for j in range(n)] for i in range(n)]\n",
    "        dic=[[-1,2],[-1,-2],[-2,-1],[-2,1],[1,2],[1,-2],[2,-1],[2,1]]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for d in dic:\n",
    "                    if i+d[0]>=0 and i+d[0]<n and j+d[1]>=0 and j+d[1]<n :\n",
    "                        lxy[i][j].append([i+d[0],j+d[1]])\n",
    "                        ls[i][j]=ls[i][j]+1/8\n",
    "        if k==1:\n",
    "            return ls[row][column]\n",
    "        lz=[]+ls\n",
    "        for _ in range(k-2):\n",
    "            lb=copy.deepcopy(lz)\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    z=0\n",
    "                    for xy in lxy[i][j]:\n",
    "                        z=z+(lb[xy[0]][xy[1]])\n",
    "                    lz[i][j]=1/8*z\n",
    "        r=0\n",
    "        for xy in lxy[row][column]:\n",
    "            r=r+lz[xy[0]][xy[1]]\n",
    "        return 1/8*r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        import copy\n",
    "        ls = [[0 for j in range(n)] for i in range(n)]\n",
    "        lxy = [[[] for j in range(n)] for i in range(n)]\n",
    "        dic = [[-1, 2], [-1, -2], [-2, -1], [-2, 1], [1, 2], [1, -2], [2, -1], [2, 1]]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for d in dic:\n",
    "                    if i + d[0] >= 0 and i + d[0] < n and j + d[1] >= 0 and j + d[1] < n:\n",
    "                        lxy[i][j].append([i + d[0], j + d[1]])\n",
    "                        ls[i][j] = ls[i][j] + 1 / 8\n",
    "        if k == 1:\n",
    "            return ls[row][column]\n",
    "        for _ in range(k - 2):\n",
    "            lb = copy.deepcopy(ls)\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    z = 0\n",
    "                    for xy in lxy[i][j]:\n",
    "                        z = z + (lb[xy[0]][xy[1]])\n",
    "                    ls[i][j] = 1 / 8 * z\n",
    "        r = 0\n",
    "        for xy in lxy[row][column]:\n",
    "            r = r + ls[xy[0]][xy[1]]\n",
    "        return 1 / 8 * r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys, os, operator\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from itertools import product, chain\n",
    "\n",
    "OFFSETS = list(chain(product({-1, 1}, {-2, 2}), product({-2, 2}, {-1, 1})))\n",
    "\n",
    "\n",
    "def get_connectivity(row, col) -> dict:\n",
    "    result = {(r * col + c): set() for r, c in product(range(row), range(col))}\n",
    "    for r, c in product(range(row), range(col)):\n",
    "        neighbors = map(lambda offset: (r + offset[0]) * col + (c + offset[1]),\n",
    "                        filter(lambda offset: 0 <= r + offset[0] < row and 0 <= c + offset[1] < col, OFFSETS))\n",
    "        neighbors = set(neighbors)\n",
    "        current = r * col + c\n",
    "        [result[current].add(n) and result[n].add(current) for n in neighbors]\n",
    "    return result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        connectivity = get_connectivity(n, n)\n",
    "        current_vertex = row * n + column\n",
    "        acc = {current_vertex: 1, }\n",
    "        for _ in range(k):\n",
    "            tmp = defaultdict(int)\n",
    "            for vertex, loop_times in acc.items():\n",
    "                for neighbor in connectivity.get(vertex):\n",
    "                    tmp[neighbor] += loop_times\n",
    "            acc = tmp\n",
    "        return sum(acc.values()) / 8 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        dirs = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]\n",
    "        cur_states = {(row, column): 1}\n",
    "        cur_states_total = 1\n",
    "        cur_probs = 1.0\n",
    "        for round in range(k):\n",
    "            print(round, cur_states, cur_states_total, cur_probs)\n",
    "            next_states = {}\n",
    "            next_states_total = 0\n",
    "            total_prob = cur_states_total * 8.0\n",
    "            stay_cnt = 0\n",
    "            for s in cur_states.keys():\n",
    "                for d in dirs:\n",
    "                    next_state_x = s[0] + d[0]\n",
    "                    next_state_y = s[1] + d[1]\n",
    "                    if 0 <= next_state_x <= n - 1 and 0 <= next_state_y <= n - 1:\n",
    "                        stay_cnt += cur_states[s]\n",
    "                        if (next_state_x, next_state_y) in next_states.keys():\n",
    "                            next_states[(next_state_x, next_state_y)] += cur_states[s]\n",
    "                        else:\n",
    "                            next_states[(next_state_x, next_state_y)] = cur_states[s]\n",
    "                        next_states_total += cur_states[s]\n",
    "            cur_states = next_states\n",
    "            cur_states_total = next_states_total\n",
    "            if total_prob > 0.0:\n",
    "                cur_probs *= (stay_cnt * 1.0) / total_prob\n",
    "            else:\n",
    "                cur_probs = 0.0\n",
    "        return cur_probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        ans = 0\n",
    "        dp = [[[0] * (n) for _ in range(n)] for _ in range(k + 1)]\n",
    "        dp[0][row][column] = 1\n",
    "        D = [(-2,-1),(-2,1),(2,-1),(2,1),(1,-2),(-1,-2),(1,2),(-1,2)]\n",
    "        for m in range(1,k + 1):\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    if dp[m - 1][x][y]:\n",
    "                        for dx,dy in D:\n",
    "                            new_x,new_y = x+ dx,y + dy\n",
    "                            if 0<=new_x<n and 0 <= new_y < n:\n",
    "                                dp[m][new_x][new_y] += dp[m-1][x][y]\n",
    "                            # else:\n",
    "                            #     ans += dp[m - 1][x][y]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans += dp[k][i][j]\n",
    "        # print(ans)\n",
    "        return ans / (8 ** k)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]\n",
    "        dp[0][row][column] = 1\n",
    "        dr = [-2, -2, 2, 2, -1, -1, 1, 1]\n",
    "        dc = [1, -1, 1, -1, 2, -2, 2, -2]\n",
    "        for i in range(1, k + 1):\n",
    "            for r in range(n):\n",
    "                for c in range(n):\n",
    "                    for idx in range(8):\n",
    "                        r_n, c_n = r + dr[idx], c + dc[idx]\n",
    "                        if 0 <= r_n < n and 0 <= c_n < n:\n",
    "                            dp[i][r][c] += dp[i - 1][r_n][c_n]\n",
    "        ans = 0\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                ans += dp[k][r][c]\n",
    "        return ans / pow(8, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, step: int, row: int, column: int) -> float:\n",
    "        directions = [[1, 2], [-1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, 1], [-2, -1]]\n",
    "        # dp[i][j][k]表示从位置 (i,j) 开始走 k 次仍在棋盘内的概率\n",
    "        dp = [[[0.0] * (step + 1) for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[i][j][0] = 1.0\n",
    "        # dp[i][j][k] = sum(dp[x][y][k-1]) / 8\n",
    "        # 其中 (x,y) 是骑士从 (i,j) 一步能到达的位置\n",
    "        for k in range(1, step + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    prob = 0.0\n",
    "                    for direction in directions:\n",
    "                        x, y = i + direction[0], j + direction[1]\n",
    "                        if 0 <= x < n and 0 <= y < n:\n",
    "                            prob += dp[x][y][k - 1]\n",
    "                    dp[i][j][k] = prob / 8\n",
    "        return dp[row][column][step]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, m: int, row: int, column: int) -> float:\n",
    "        if m==0:\n",
    "            return 1.0\n",
    "        dp=[[[0.0]*n for _ in range(n)] for _ in range(m+1)]\n",
    "        points=[[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]]\n",
    "        dp[0][row][column]=1.0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if dp[i][j][k]==0.0:\n",
    "                        continue\n",
    "                    for nx, ny in points:\n",
    "                        r,c=j+nx,k+ny\n",
    "                        if r>=0 and r<n and c>=0 and c<n:\n",
    "                            dp[i+1][r][c]+=dp[i][j][k]/8\n",
    "        ans=0\n",
    "        for j in range(n):\n",
    "            for k in range(n):\n",
    "                ans+=dp[m][j][k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n, k, row, column):\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        if n == None or k == None or row == None or column == None:\n",
    "            return 0 \n",
    "        \n",
    "        dp = [[[-1 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]\n",
    "        return self.process(row, column, k, n, dp)\n",
    "        \n",
    "    def process(self, cur_row, cur_col, left_k, n, dp):\n",
    "        \"\"\"\n",
    "        处于[cur_row, cur_col]的位置, 剩余步骤left_k的状态下, 最终骑士仍然在棋盘上的概率\n",
    "        Args:\n",
    "            cur_row (int): 行索引\n",
    "            cur_col (int): 列索引\n",
    "            left_k (int): 剩余步数\n",
    "            n (int): 棋盘大小\n",
    "        returns (float): 最终的概率\n",
    "        \"\"\"\n",
    "        #递归出口\n",
    "        if not self.isValid(cur_row, cur_col, n):\n",
    "            return 0\n",
    "        else:\n",
    "            if left_k == 0:\n",
    "                return 1 \n",
    "        \n",
    "        #若已经访问过了该状态直接返回\n",
    "        if dp[cur_row][cur_col][left_k] != -1:\n",
    "            return dp[cur_row][cur_col][left_k]\n",
    "        \n",
    "        directions = [(2, 1), (1, 2), (-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1)]\n",
    "        p = 0 \n",
    "        for direction in directions:\n",
    "            new_row = cur_row + direction[0]\n",
    "            new_col = cur_col + direction[1]\n",
    "            p += self.process(new_row, new_col, left_k - 1, n, dp) / 8.0\n",
    "        \n",
    "        #更新dp\n",
    "        dp[cur_row][cur_col][left_k] = p \n",
    "        #return\n",
    "        return p\n",
    "\n",
    "    def isValid(self, cur_row, cur_col, n):\n",
    "        \"\"\"\n",
    "        判断坐标是否合法\n",
    "        \"\"\"\n",
    "        if 0 <= cur_row < n and 0 <= cur_col < n:\n",
    "            return True \n",
    "        else:\n",
    "            return False \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        self.directions = [(2, 1), (-2, 1), (2, -1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]\n",
    "        self.mem = [[[0] * (k+1) for i in range(n)] for i in range(n)]\n",
    "        return self.backtracking(n, k, row, column)\n",
    "        \n",
    "\n",
    "    def backtracking(self, n, k, i, j):\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if self.mem[i][j][k] != 0:\n",
    "            return self.mem[i][j][k]\n",
    "        res = 0\n",
    "        for direction in self.directions:\n",
    "            nxt_i = i + direction[0]\n",
    "            nxt_j = j + direction[1]\n",
    "            if nxt_i >=0 and nxt_i< n and nxt_j >= 0 and nxt_j < n:\n",
    "                res += self.backtracking(n, k-1, nxt_i, nxt_j)/8\n",
    "        self.mem[i][j][k] = res\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(k+1)]\n",
    "        dp [0][row][column] = 1\n",
    "        directions = [(-2, 1), (-2, -1), (2, 1), (2, -1), (-1, -2), (-1, 2), (1, -2), (1, 2)]\n",
    "\n",
    "        for step in range(k):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if dp[step][i][j] != 0:\n",
    "                        for dr, dc in directions:\n",
    "                            nr, nc = dr + i, dc + j\n",
    "                            if 0 <= nr < n and 0 <= nc < n:\n",
    "                                dp[step+1][nr][nc] += dp[step][i][j] / 8\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res += dp[k][i][j]\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        f = [[[0] * n for _ in range(n)] for _ in range(k + 1)]\n",
    "        def dfs(i, j, k):\n",
    "            if j < 0 or j >= n or k < 0 or k >= n: return 0\n",
    "            if i == 0:  return 1.0\n",
    "            if f[i][j][k] != 0: return f[i][j][k]\n",
    "            ans = 0\n",
    "            for x, y in [(j + 1, k - 2), (j + 2, k - 1), (j + 1, k + 2), (j + 2, k + 1), (j - 1, k + 2), (j - 2, k + 1), (j - 1, k - 2), (j - 2, k - 1)]:\n",
    "                ans += dfs(i - 1, x, y) / 8.0\n",
    "            f[i][j][k] = ans\n",
    "            return ans\n",
    "        return dfs(k, row, column)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]\n",
    "        dp[0][row][column] = 1\n",
    "        for step in range(1, k + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if 0 <= ni < n and 0 <= nj < n: dp[step][i][j] += dp[step - 1][ni][nj]\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n): \n",
    "                cnt += dp[k][i][j]\n",
    "        return cnt / (8 ** k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dirs = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]\n",
    "        dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]\n",
    "        dp[row][column][0] = 1\n",
    "        for t in range(k + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for dx, dy in dirs:\n",
    "                        nx = i-dx\n",
    "                        ny = j-dy\n",
    "                        if 0 <= nx < n and 0 <= ny < n:\n",
    "                            dp[i][j][t] += dp[i - dx][j - dy][t-1] / 8\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res += dp[i][j][-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, K: int, row: int, column: int) -> float:\n",
    "        f = [[[0] * (K + 1) for _ in range(n + 1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                f[i][j][K] = 1\n",
    "        dx = [-2, -1, 1, 2, 2, 1, -1, -2]\n",
    "        dy = [1, 2, 2, 1, -1 ,-2, -2, -1]\n",
    "        for k in range(K - 1, -1, -1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for u in range(8):\n",
    "                        a = i + dx[u]\n",
    "                        b = j + dy[u]\n",
    "                        if 0 <= a < n and 0 <= b < n:\n",
    "                            f[i][j][k] += f[a][b][k + 1] / 8\n",
    "        return f[row][column][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        '''\n",
    "        留在棋盘的概率，从当前点出发走k步能达到的所有坐标点，\n",
    "        dp[i][j][p]代表从位置[i,j]出发，使用步数不超过p步，最后仍在棋盘内的概率\n",
    "        '''\n",
    "        dirs = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)]\n",
    "        dp = [[[0 for _ in range(k+1)] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[i][j][0] = 1\n",
    "\n",
    "        for p in range(1, k+1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for d in dirs:\n",
    "                        nx, ny = i+d[0], j+d[1]\n",
    "                        if nx<0 or nx>=n or ny<0 or ny>=n:\n",
    "                            continue\n",
    "                        dp[i][j][p] += dp[nx][ny][p-1] / 8\n",
    "        return dp[row][column][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]\n",
    "        for step in range(k + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if step == 0:\n",
    "                        dp[step][i][j] = 1\n",
    "                    else:\n",
    "                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):\n",
    "                            ni, nj = i + di, j + dj\n",
    "                            if 0 <= ni < n and 0 <= nj < n:\n",
    "                                dp[step][i][j] += dp[step - 1][ni][nj] / 8\n",
    "        return dp[k][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]\n",
    "        for step in range(k + 1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if step == 0:\n",
    "                        dp[step][i][j] = 1\n",
    "                    else:\n",
    "                        for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)):\n",
    "                            ni, nj = i + di, j + dj\n",
    "                            if 0 <= ni < n and 0 <= nj < n:\n",
    "                                dp[step][i][j] += dp[step - 1][ni][nj] / 8\n",
    "\n",
    "        return dp[k][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flat(self, row, col, n):\n",
    "        return row * n + col\n",
    "    \n",
    "    def coord(self, pos, n):\n",
    "        return (pos // n, pos % n)\n",
    "\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dirs = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]\n",
    "        pos_map = defaultdict(list)\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                for x_dir, y_dir in dirs:\n",
    "                    new_row = r + y_dir\n",
    "                    new_col = c + x_dir\n",
    "                    if 0 <= new_row < n and 0 <= new_col < n:\n",
    "                        pos_map[(r, c)].append((new_row, new_col))\n",
    "        \n",
    "        dp = [[0.0] * (k + 1) for _ in range(n * n)]\n",
    "        dp[self.flat(row, column, n)][0] = 1.0\n",
    "\n",
    "        for k_step in range(1, k + 1):\n",
    "            for r in range(n):\n",
    "                for c in range(n):\n",
    "                    for (prev_r, prev_c) in pos_map[(r, c)]:\n",
    "                        dp[self.flat(r, c, n)][k_step] += dp[self.flat(prev_r, prev_c, n)][k_step - 1] * 0.125\n",
    "                        \n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                res += dp[self.flat(r, c, n)][k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dp = []\n",
    "\n",
    "    def init(self, n, k):\n",
    "        Solution.dp = [[[-1 for i in range(n)] for j in range(n)] for m in range(k)]\n",
    "\n",
    "    def inBoard(self, n, row, column):\n",
    "        return row > -1 and column > -1 and row < n and column < n\n",
    "\n",
    "    def dfs(self, n, k, row, column):\n",
    "        res = 0\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        rc = [\n",
    "            [-1, -2],\n",
    "            [-2, -1],\n",
    "            [-2, 1],\n",
    "            [-1, 2],\n",
    "            [1, 2],\n",
    "            [2, 1],\n",
    "            [2, -1],\n",
    "            [1, -2]\n",
    "        ]\n",
    "        \n",
    "        for i in range(8):\n",
    "            r = row + rc[i][0]\n",
    "            c = column + rc[i][1]\n",
    "            if not self.inBoard(n, r, c):\n",
    "                continue\n",
    "            \n",
    "            if Solution.dp[k-1][r][c] != -1:\n",
    "                res += Solution.dp[k-1][r][c]\n",
    "            else:\n",
    "                tmp = self.dfs(n, k-1, r, c)\n",
    "                Solution.dp[k-1][r][c] = tmp\n",
    "                res += tmp\n",
    "            \n",
    "            \n",
    "        \n",
    "        return res\n",
    "\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        self.init(n, k)\n",
    "        res = self.dfs(n, k, row, column)\n",
    "        return float(res)/8**k\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp=[[[0 for i in range(n)]for i in range(n)]for i in range(k+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[0][i][j]=1\n",
    "        # x=self.process(n,k,row,column,dp)/pow(8,k)\n",
    "        # y=1\n",
    "        return self.process(n,k,row,column,dp)/pow(8,k)\n",
    "    \n",
    "    \n",
    "    def process(self,n:int,step:int,x:int,y:int,dp)->int:\n",
    "        for h in range(1,step+1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i-1,j+2,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i-1,j-2,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i+1,j-2,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i+1,j+2,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i+2,j+1,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i+2,j-1,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i-2,j+1,dp)\n",
    "                    dp[h][i][j]+=self.getDP(n,h-1,i-2,j-1,dp)\n",
    "\n",
    "        return dp[step][x][y]\n",
    "\n",
    "    def getDP(self,n:int,step:int,x:int,y:int,dp)->int:\n",
    "        if(x<0 or x>=n or y<0 or y>=n):\n",
    "            return 0\n",
    "        return dp[step][x][y]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        moves = [[-1, -2], [-2, -1], [1, -2], [2, -1], \n",
    "                [-1, 2], [-2, 1], [1, 2], [2, 1]]\n",
    "\n",
    "        # dp initialization and base case\n",
    "        dp = [[[0]*(k+1) for _ in range(n+4)] for _ in range(n+4)]\n",
    "        # for i in range(n+4):\n",
    "        #     for j in range(n+4):\n",
    "        #         if i <=1 or i>=n+2 or j <= 1 or j>= n+2:\n",
    "        #             dp[i][j][0] = 1\n",
    "        # print(dp)\n",
    "\n",
    "        def traverse(i, j, k):\n",
    "            # print(i, j, k)\n",
    "            if i <=1 or i>=n+2 or j <= 1 or j>= n+2:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if dp[i][j][k] != 0:\n",
    "                return dp[i][j][k]\n",
    "            for move in moves:\n",
    "                dp[i][j][k] +=  1/8 * traverse(i-move[0], j-move[1], k-1)\n",
    "            return dp[i][j][k]\n",
    "        \n",
    "        res = traverse(row+2, column+2, k)\n",
    "        return 1-res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        cache = [[[-1] * (k+1) for _ in range(n+1) ] for _ in range(n+1)]\n",
    "        def dfs(i, r, c):\n",
    "            if r < 0 or r >= n or c < 0 or c >= n:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            if cache[r][c][i] != -1:\n",
    "                return cache[r][c][i]\n",
    "            res = 0\n",
    "            for x, y in ((-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2)):\n",
    "                res += dfs(i-1, r + x, c + y)\n",
    "            cache[r][c][i] = res\n",
    "            return res\n",
    "        r = dfs(k, row, column)\n",
    "        \n",
    "        return r/pow(8, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 保存算过的数\n",
    "        self.pro_dict = defaultdict(float)\n",
    "\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        _hash = k * 1e4 + row * 1e2 + column\n",
    "        if self.pro_dict[_hash]:\n",
    "            return self.pro_dict[_hash]\n",
    "        if 0 <= row <= n-1 and 0 <= column <= n-1:\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            # direction横向纵向，row_positive negative正负， col_positive negative正负\n",
    "            for direction in range(1, 3):\n",
    "                for row_pn in range(-1, 2, 2):\n",
    "                    for col_pn in range(-1, 2, 2):\n",
    "                        new_row, new_column = row + direction * row_pn, column + (3 - direction) * col_pn\n",
    "                        res += 1/8 * self.knightProbability(n, k-1, new_row, new_column)\n",
    "            # 递归最重要的一部分：不要干重复的活儿！\n",
    "            self.pro_dict[_hash] = res\n",
    "            return res\n",
    "\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        memo = [[[0] * (k + 1) for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        DIRS = ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2))\n",
    "\n",
    "        def dfs(r, c, step):\n",
    "            if 0 > r or r >= n or 0 > c or c >= n:\n",
    "                return 0\n",
    "            \n",
    "            if step == 0:\n",
    "                return 1\n",
    "            \n",
    "\n",
    "            \n",
    "            if memo[r][c][step] != 0:\n",
    "                return memo[r][c][step]\n",
    "            \n",
    "            res = 0\n",
    "\n",
    "            for dr, dc in DIRS:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                res += dfs(nr, nc, step - 1) / 8\n",
    "            \n",
    "            memo[r][c][step] = res\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        ans = dfs(row, column, k)\n",
    "        \n",
    "        print(memo)\n",
    "\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dr = [[-2, -1], [-2, 1], [2, -1], [2, 1], [-1, -2], [1, -2], [-1, 2], [1, 2]]\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0] * (n+10) for _ in range(n+10)] for _ in range((1+k))]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[0][i][j] = 1\n",
    "\n",
    "        for st in range(1, k+1):\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    tmp = 0\n",
    "                    for di, dj in dr:\n",
    "                        tmp += dp[st-1][i+di][j+dj]\n",
    "                    dp[st][i][j] = tmp / 8\n",
    "        return dp[k][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dmoves = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]\n",
    "\n",
    "        memo = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)]\n",
    "\n",
    "        def dfs(i: int, j: int, remaining_steps: int) -> float:\n",
    "            if not (0 <= i < n and 0 <= j < n):\n",
    "                return 0\n",
    "            elif remaining_steps <= 0:\n",
    "                return 1\n",
    "            elif memo[remaining_steps][i][j] != 0:\n",
    "                return memo[remaining_steps][i][j]\n",
    "            # print(\"{:>2}, {:>2}, remaining: {}\".format(i, j, remaining_steps))\n",
    "            options = [dfs(i + di, j + dj, remaining_steps - 1) for di, dj in dmoves]\n",
    "            # print(options)\n",
    "            prob = sum(options) / len(dmoves)\n",
    "            memo[remaining_steps][i][j] = prob\n",
    "            return prob\n",
    "        return dfs(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        ops = [[-1, -2], [-2, -1], [-1, 2], [-2, 1], [1, 2], [2, 1], [1, -2], [2, -1]]\n",
    "        dp = [[[0 for z in range(n)] for y in range(n)] for x in range(k + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dp[k][i][j] = 1\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            for x in range(n):\n",
    "                for y in range(n):\n",
    "                    for op in ops:\n",
    "                        if (x + op[0] >= 0 and x + op[0] <= n - 1) and (y + op[1] >= 0 and y + op[1] <= n - 1):\n",
    "                            dp[i][x][y] += dp[i + 1][x + op[0]][y + op[1]]\n",
    "        return dp[0][row][column] * 1.0 / (8**k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0]*n for _ in range(n)]for _ in range(k+1)]\n",
    "        for i in range(k+1):\n",
    "            for j in range(n):\n",
    "                for g in range(n):\n",
    "                    if i == 0:\n",
    "                        dp[i][j][g] = 1\n",
    "                    else:\n",
    "                        for d1,d2 in [(1,2),(-1,2),(2,1),(-2,1),(1,-2),(-1,-2),(2,-1),(-2,-1)]:\n",
    "                            if j + d1 <n and g + d2 < n and j + d1 >= 0 and g + d2 >= 0:\n",
    "                                dp[i][j][g] += dp[i-1][j+d1][g+d2]/8\n",
    "\n",
    "                                \n",
    "        print(dp)\n",
    "        return dp[k][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        def next_pos(pos):\n",
    "            a,b = pos[0],pos[1]\n",
    "            res = []\n",
    "            for p in [(a-2,b+1),(a-2,b-1),(a+2,b+1),(a+2,b-1),(a+1,b-2),(a-1,b-2),(a+1,b+2),(a-1,b+2)]:\n",
    "                if 0 <= p[0] <= n-1 and 0 <= p[1] <= n-1:\n",
    "                    res.append(p)\n",
    "            return res\n",
    "\n",
    "        # 01\n",
    "        dp = [{} for _ in range(k+1)] # dp[k]为字典，表示走了k步后，到达各个点的path数\n",
    "\n",
    "        # 02\n",
    "        dp[0] = {(row,column):1}\n",
    "\n",
    "\n",
    "        # 03\n",
    "        for step in range(1,k+1):\n",
    "            print(step)\n",
    "            for pos in list(dp[step-1].keys()):\n",
    "                times = dp[step-1][pos] # 第step-1步中pos被访问次数\n",
    "                for next in next_pos(pos):\n",
    "                \n",
    "                    if next not in dp[step]: \n",
    "                        print('sss')\n",
    "                        # 判断next是否为dp[step]的一个key\n",
    "                        dp[step][next] = times\n",
    "                        print(next)\n",
    "                    else:\n",
    "                        dp[step][next] += times\n",
    "                \n",
    "\n",
    "        path_num = sum(list(dp[-1].values()))\n",
    "                \n",
    "        return path_num/8**k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if row < 0 or row >= n or column < 0 or column >= n:\n",
    "            return 0\n",
    "        \n",
    "        if k == 0:\n",
    "            return 1\n",
    "\n",
    "        moves = [\n",
    "            (1, 2), (2, 1), (2, -1), (1, -2),\n",
    "            (-1, -2), (-2, -1), (-2, 1), (-1, 2)\n",
    "        ]\n",
    "\n",
    "        prob = 0\n",
    "        for dx, dy in moves:\n",
    "            x, y = row + dx, column + dy\n",
    "            \n",
    "            if (k-1, x, y) not in self.memo:\n",
    "                self.memo[(k-1, x, y)] = self.knightProbability(n, k-1, x, y)\n",
    "            \n",
    "            prob += 1 / 8 * self.memo[(k-1, x, y)]\n",
    "            \n",
    "        return prob\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        ds = ((-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r, c, k):\n",
    "            if not (0 <= r < n and 0 <= c < n):\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            return sum(dp(r + dr, c + dc, k - 1) for dr, dc in ds) / 8\n",
    "\n",
    "        dpa = dp(row, column, k)\n",
    "\n",
    "        dp.cache_clear()\n",
    "        return dpa\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        global memo \n",
    "        global N \n",
    "        global dirs\n",
    "        N = n  \n",
    "        dirs = []\n",
    "        for i in [-1,1]:\n",
    "            for j in [-2,2]:\n",
    "                dirs.append((i,j))\n",
    "                dirs.append((j,i))\n",
    "        n = n \n",
    "        # state(k,row,column)\n",
    "        memo = {}\n",
    "        return dp(k,row,column)\n",
    "\n",
    "memo = {}\n",
    "N = 0 \n",
    "dirs = []\n",
    "\n",
    "# return the probability of board inside boundary at (k,row,col)\n",
    "def dp(k: int, row: int, col:int) -> float:\n",
    "    global memo\n",
    "    global N  \n",
    "    global dirs\n",
    "    if (k,row,col) in memo:\n",
    "        return memo[(k,row,col)]\n",
    "    cur = (k,row,col)\n",
    "    # base cases \n",
    "    # exceeding boundary \n",
    "    if row < 0 or row >= N or col < 0 or col >= N:\n",
    "        memo[cur] = 0.0\n",
    "        return 0.0 \n",
    "    # reach the end \n",
    "    if k == 0:\n",
    "        memo[cur] = 1.0\n",
    "        return 1.0 \n",
    "\n",
    "    # traversal \n",
    "    ans = 0 \n",
    "    for dx, dy in dirs:\n",
    "        # 8 directions, each divided by 8 \n",
    "        ans += dp(k-1, row+dx,col+dy)/8.0\n",
    "    # save result \n",
    "    memo[cur] = ans \n",
    "    return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0]*n for _ in range(n)] for _ in range(k+1)]\n",
    "        for step in range(k+1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if step == 0:\n",
    "                        dp[step][i][j] = 1\n",
    "                    else:\n",
    "                        for di, dj in [[2, 1], [2, -1], [-2, 1], [-2, -1],\n",
    "                                       [1, 2], [1, -2], [-1, 2], [-1, -2]]:\n",
    "                            if 0<=i+di<n and 0<=j+dj<n:\n",
    "                                dp[step][i][j] += dp[step-1][i+di][j+dj]*(1/8)\n",
    "        print(dp)\n",
    "        return dp[k][row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dirs = [[2,1],[1,2],[-2,1],[-1,2],[-2,-1],[-1,-2],[1,-2],[2,-1]]\n",
    "        @cache\n",
    "        def back(x,y,k):\n",
    "            if x < 0 or y < 0 or x >= n or y >= n:return 0\n",
    "            if k == 0:return 1\n",
    "            res = 0\n",
    "            for i,j in dirs:\n",
    "                res += back(x+i,y+j,k-1)\n",
    "            return res\n",
    "        res = back(row,column,k)/8**k\n",
    "        del back\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, row, column, n):\n",
    "        if row >= 0 and row <= n - 1 and column >= 0 and column <= n - 1:\n",
    "            return True\n",
    "        return False\n",
    "    def cal(self, row, column, n, count, k, visited):\n",
    "        res = 0\n",
    "        if self.check(row, column, n) and count == k:\n",
    "            return (1/8) ** count\n",
    "        if self.check(row, column, n) and count < k:\n",
    "            for i in [(1, 2), (2, 1), (-1, -2), (-2, -1), (-1, 2), (-2, 1), (2, -1), (1, -2)]:\n",
    "                if (row + i[0], column + i[1], n, count + 1, k) not in visited:\n",
    "                    visited[(row + i[0], column + i[1], n, count + 1, k)] = self.cal(row + i[0], column + i[1], n, count + 1, k, visited)\n",
    "                    res += visited[(row + i[0], column + i[1], n, count + 1, k)]\n",
    "                else:\n",
    "                    res += visited[(row + i[0], column + i[1], n, count + 1, k)]\n",
    "        return res\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        visited = {}\n",
    "        visited[(row, column, n, 0, k)] = 1\n",
    "        return self.cal(row, column, n, 0, k, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "\n",
    "        if k==0:\n",
    "            return 1\n",
    "        global mark\n",
    "        mark = {}\n",
    "        def solve(n,k,x,y):\n",
    "            global mark\n",
    "            if (x,y,k) in mark:\n",
    "                return mark[(x,y,k)]\n",
    "            if k==1:\n",
    "                poss = 0\n",
    "                if x-1>=0 and y-2>=0:\n",
    "                    poss += 1\n",
    "                if x-2>=0 and y-1>=0:        \n",
    "                    poss += 1\n",
    "                if x-2>=0 and y+1<n:\n",
    "                    poss += 1\n",
    "                if x-1>=0 and y+2<n:\n",
    "                    poss += 1\n",
    "                if x+1<n and y+2<n:\n",
    "                    poss += 1\n",
    "                if x+2<n and y+1<n:\n",
    "                    poss += 1\n",
    "                if x+2<n and y-1>=0:\n",
    "                    poss += 1\n",
    "                if x+1<n and y-2>=0:\n",
    "                    poss += 1\n",
    "                mark[(x,y,k)]=poss/8\n",
    "                return poss/8\n",
    "            else:\n",
    "                poss = 0\n",
    "                target_x = x-1\n",
    "                target_y = y-2\n",
    "                if target_x>=0 and target_y>=0:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x-2\n",
    "                target_y = y-1\n",
    "                if target_x>=0 and target_y>=0:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x-2\n",
    "                target_y = y+1\n",
    "                if target_x>=0 and target_y<n:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x-1\n",
    "                target_y = y+2\n",
    "                if target_x>=0 and target_y<n:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x+1\n",
    "                target_y = y+2\n",
    "                if target_x<n and target_y<n:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x+2\n",
    "                target_y = y+1\n",
    "                if target_x<n and target_y<n:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x+2\n",
    "                target_y = y-1\n",
    "                if target_x<n and target_y>=0:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "\n",
    "                target_x = x+1\n",
    "                target_y = y-2\n",
    "                if target_x<n and target_y>=0:\n",
    "                    if (target_x,target_y,k-1) in mark:\n",
    "                        poss += mark[(target_x,target_y,k-1)]/8\n",
    "                    else:\n",
    "                        poss += solve(n,k-1,target_x,target_y)/8\n",
    "                mark[(x,y,k)]=poss\n",
    "                return poss\n",
    "        res = solve(n,k,row,column)\n",
    "        print(mark)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    nextSteps = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "        return self.knightNext(r, c, N, K)\n",
    "\n",
    "    @functools.lru_cache(None)\n",
    "    def knightNext(self, r, c, N, time):\n",
    "        if time <= 0:         \n",
    "            return 1\n",
    "        sum = 0\n",
    "        for nextStep in self.nextSteps:\n",
    "            new_r = r + nextStep[0]\n",
    "            new_c = c + nextStep[1]\n",
    "            if new_r >= 0 and new_r <= N-1 and new_c >= 0 and new_c <= N-1:\n",
    "                sum += self.knightNext(new_r, new_c, N, time-1)\n",
    "        return sum / 8.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "        row, col = N, N\n",
    "\n",
    "        def get_surround(x, y):\n",
    "            surround = [(-2, -1), (-2, 1), (-1, -2), (1, -2), (2, -1), (2, 1), (-1, 2), (1, 2)]\n",
    "            for dx, dy in surround:\n",
    "                yield x + dx, y + dy\n",
    "\n",
    "        # 坐标验证\n",
    "        def available(m, n):\n",
    "            return 0 <= m < row and 0 <= n < col\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, steps):\n",
    "            one_part = 1 / 8\n",
    "\n",
    "            if available(x, y):\n",
    "                if steps <= 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    ans = 0\n",
    "                    for x1, y1 in get_surround(x, y):\n",
    "                        ans += one_part * dfs(x1, y1, steps - 1)\n",
    "\n",
    "                    return ans\n",
    "\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return dfs(r, c, K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dpall(k,x,y,n,dp):\n",
    "    if dp[k][x][y] >0:\n",
    "        return dp[k][x][y]\n",
    "    if x>=n or x<0 or y>=n or y<0:\n",
    "        dp[k][x][y] = 0\n",
    "        return 0\n",
    "    if k == 0:\n",
    "        dp[k][x][y] =1\n",
    "        return 1\n",
    "    dp[k][x][y] = 1/8 *dpall(k-1,x+1,y+2,n,dp) +1/8 *dpall(k-1,x+1,y-2,n,dp) + 1/8 *dpall(k-1,x+2,y+1,n,dp) +1/8 *dpall(k-1,x+2,y-1,n,dp) +1/8 *dpall(k-1,x-1,y+2,n,dp) +1/8 *dpall(k-1,x-1,y-2,n,dp) + 1/8 *dpall(k-1,x-2,y+1,n,dp) + 1/8 *dpall(k-1,x-2,y-1,n,dp)\n",
    "    return dp[k][x][y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        dp = [[[0 for w in range(-n,2*n)]for s in range(-n,2*n)]for i in range(k+1)]\n",
    "\n",
    "        return dpall(k,row,column,n,dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, K: int, row: int, column: int) -> float:\n",
    "        dx = [-2, -1, 1, 2, 2, 1, -1, -2]\n",
    "        dy = [1, 2, 2, 1, -1, -2, -2, -1]\n",
    "        # 移动k步位置在（i，j）的概率，（i，j）不出界。\n",
    "        f = [[[0] * (K + 1) for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                f[i][j][K] = 1\n",
    "\n",
    "        for k in range(K - 1, -1, -1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for u in range(8):\n",
    "                        a = i + dx[u]\n",
    "                        b = j + dy[u]\n",
    "                        if 0 <= a < n and 0 <= b < n:\n",
    "                            f[i][j][k] += (f[a][b][k + 1] / 8)\n",
    "        print(f)\n",
    "        return f[row][column][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        @lru_cache(maxsize=8192)\n",
    "        def count(n, k, row, col):\n",
    "            if k == 0:\n",
    "                return 1\n",
    "\n",
    "            result = 0\n",
    "\n",
    "            for r_, c_ in [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]:\n",
    "                r = row + r_\n",
    "                c = col + c_\n",
    "\n",
    "                if 0 <= r < n and 0 <= c < n:\n",
    "                    result += count(n, k - 1, r, c)\n",
    "            \n",
    "            return result\n",
    "\n",
    "        return count(n, k, row, column) / (8 ** k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "move_lst = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        # return self._dfs(n, k, row, column, 0)\n",
    "        return self._tt(n, k, row, column)\n",
    "    def _tt(self, n: int, k: int, row: int, column: int):\n",
    "        # k=0时，无论在什么位置，都是概率为1，且8个方向都可以走\n",
    "        self.record_d = {0: {(i, j): 1 for i in range(n) for j in range(n)}}\n",
    "        for kk in range(1, k + 1):\n",
    "            self.record_d[kk] = {}\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    v = 0\n",
    "                    for move_r, move_c in move_lst:\n",
    "                        # 表示移动到棋盘内\n",
    "                        if i + move_r in range(n) and j + move_c in range(n):\n",
    "                            # 可以走的位置\n",
    "                            v += self.record_d[kk - 1][(i + move_r, j + move_c)] / 8\n",
    "                    self.record_d[kk][(i, j)] = v\n",
    "        return self.record_d[k][(row, column)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, K: int, row: int, column: int) -> float:\n",
    "        f = [[[0] * (K + 1) for _ in range(n + 1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                f[i][j][K] = 1\n",
    "        dx = [-2, -1, 1, 2, 2, 1, -1, -2]\n",
    "        dy = [1, 2, 2, 1, -1, -2, -2, -1]\n",
    "        for k in range(K - 1, -1, -1):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    for u in range(8):\n",
    "                        a = i + dx[u]\n",
    "                        b = j + dy[u]\n",
    "                        if 0 <= a < n and 0 <= b < n:\n",
    "                            f[i][j][k] += f[a][b][k + 1] / 8\n",
    "        print(f)\n",
    "        return f[row][column][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "        actions = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [-1, 2], [1, -2], [-1, -2]]\n",
    "        self.inarea = 0\n",
    "        #memo = {}\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j, k):\n",
    "            #if (i, j, k) in memo:\n",
    "            #    return memo[i, j, k]\n",
    "            if i < 0 or j < 0 or i >= N or j >= N:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for a, b in actions:\n",
    "                x, y = i+a, j+b\n",
    "                ans += dfs(x, y, k-1)\n",
    "            #memo[i, j, k] = ans\n",
    "            return ans\n",
    "        ans = dfs(r, c, K)\n",
    "        return ans / (8 ** K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k == 0:\n",
    "            if 0 <= row < n and 0 <= column < n:\n",
    "                return 1.0\n",
    "            else:\n",
    "                return 0.0\n",
    "\n",
    "\n",
    "        dp = [[[[-1, -1] for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]\n",
    "        directions = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, -2], [2, -1], [2, 1], [1, 2]]\n",
    "\n",
    "        def dfs(n: int, k: int, x: int, y: int, dp: List[List[List[List[int]]]]) -> (int, int):\n",
    "            if dp[x][y][k][0] != -1 and dp[x][y][k][1] != -1:\n",
    "                return (dp[x][y][k][0], dp[x][y][k][1])\n",
    "\n",
    "            if k == 0:\n",
    "                if x >= 0 and x < n and y >= 0 and y < n:\n",
    "                    dp[x][y][0][0], dp[x][y][0][1] = 1, 0\n",
    "                else:\n",
    "                    dp[x][y][0][0], dp[x][y][0][1] = 0, 0\n",
    "                return (dp[x][y][k][0], dp[x][y][k][1])\n",
    "\n",
    "            stay, depart = 0, 0\n",
    "            for dir in directions:\n",
    "                nx, ny = x + dir[0], y + dir[1]\n",
    "\n",
    "                if nx >= 0 and nx < n and ny >= 0 and ny < n:\n",
    "                    xs, xd = dfs(n, k - 1, nx, ny, dp)\n",
    "                    stay += xs\n",
    "                    depart += xd\n",
    "                else:\n",
    "                    xs, xd = 0, math.pow(8, k - 1)\n",
    "                    stay += xs\n",
    "                    depart += xd\n",
    "\n",
    "            dp[x][y][k][0] = stay\n",
    "            dp[x][y][k][1] = depart\n",
    "            return (stay, depart)\n",
    "\n",
    "        dfs(n, k, row, column, dp)\n",
    "\n",
    "        return dp[row][column][k][0] / (dp[row][column][k][0] + dp[row][column][k][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(kk, rr, cc):\n",
    "            if kk == 0:\n",
    "                return 1.0 if rr == r and cc == c else 0.0\n",
    "\n",
    "            ans = 0.0\n",
    "            for new_r, new_c in [(rr-1, cc-2), (rr+1, cc-2), (rr-1, cc+2), (rr+1, cc+2),\n",
    "                                     (rr-2, cc-1), (rr+2, cc-1), (rr-2, cc+1), (rr+2, cc+1)]:\n",
    "                if new_r >= 0 and new_r < N and new_c >= 0 and new_c < N:\n",
    "                    ans += dp(kk-1, new_r, new_c) / 8\n",
    "            return ans\n",
    "\n",
    "        ans = 0.0\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                ans += dp(K, i, j)\n",
    "        del dp\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        def prob(n, i, r, c, buf={}):\n",
    "            if r < 0 or r >= n or c < 0 or c >= n:\n",
    "                return 0\n",
    "            elif i == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                key = i*n*n+r*n+c\n",
    "                p = buf.get(key, None)\n",
    "                if p is None:\n",
    "                    p = 0\n",
    "                    for dr, dc in [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]:\n",
    "                        p += prob(n, i-1, r+dr, c+dc, buf) / 8\n",
    "                    buf[key] = p\n",
    "                return p\n",
    "        return prob(n,k,row,column)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, r: int, c: int) -> float:\n",
    "        d=[(i,j) for i,j in product([-1,1,2,-2],repeat=2) if i!=j and i+j]\n",
    "        @cache\n",
    "        def f(i,j,k):\n",
    "            if i>j : return f(j,i,k)\n",
    "            if i<0 or j>=n : return 0\n",
    "            if k==0: return 1.0 \n",
    "            return sum(f(i+x,j+y,k-1) for x,y in d)/8\n",
    "        return f(r,c,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import time\n",
    " \n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:\n",
    "        # Add memoization technique.\n",
    "        nextcell = defaultdict(list)\n",
    "        for r in range(n):\n",
    "            for c in range(n):                \n",
    "                r_tmp,c_tmp = r+1,c+2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))\n",
    "                r_tmp,c_tmp = r+2,c+1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r+2,c-1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                                    \n",
    "                r_tmp,c_tmp = r+1,c-2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-1,c-2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-2,c-1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-2,c+1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-1,c+2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    " \n",
    "        memo = dict()\n",
    "                \n",
    "        def dp(row,col,k):        \n",
    "            if (row,col,k) in memo:\n",
    "                return memo[(row,col,k)]\n",
    "            if k == 0:\n",
    "                return 1 if row >= 0 and row < n and col >= 0 and col < n else 0\n",
    "            if row < 0 or col < 0 or row >= n or col >= n:\n",
    "                return 0\n",
    "            nxt = nextcell[(row,col)]\n",
    "            p   = 0\n",
    "            # print(nxt)\n",
    "            for m in range(8):\n",
    "                # print(m)\n",
    "                if m >= len(nxt):\n",
    "                    print(row,col,k,m,nxt)\n",
    "                cellnext = nxt[m]\n",
    "                p = p + dp(cellnext[0],cellnext[1],k-1)/8\n",
    "            # print('dp({0},{1},{2} = {3})'.format(row,col,k,p))\n",
    "            memo[(row,col,k)] = p\n",
    "            return p\n",
    " \n",
    "        return dp(row,col,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, col: int) -> float:\n",
    "        nextcell = defaultdict(list)\n",
    "        for r in range(n):\n",
    "            for c in range(n):                \n",
    "                r_tmp,c_tmp = r+1,c+2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))\n",
    "                r_tmp,c_tmp = r+2,c+1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r+2,c-1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                                    \n",
    "                r_tmp,c_tmp = r+1,c-2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-1,c-2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-2,c-1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-2,c+1\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "                r_tmp,c_tmp = r-1,c+2\n",
    "                nextcell[(r,c)].append(((r_tmp if r_tmp>=0 and r_tmp<n else -1), (c_tmp if c_tmp>=0 and c_tmp<n else -1)))                                    \n",
    "\n",
    "        memo = dict()\n",
    "                \n",
    "        def dp(row,col,k):        \n",
    "            if (row,col,k) in memo:\n",
    "                return memo[(row,col,k)]\n",
    "            if row < 0 or col < 0:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1 if row >= 0 and row < n and col >= 0 and col < n else 0\n",
    "            nxt = nextcell[(row,col)]\n",
    "            p   = 0\n",
    "            # print(nxt)\n",
    "            for m in range(8):\n",
    "                # print(m)\n",
    "                if m >= len(nxt):\n",
    "                    print(row,col,k,m,nxt)\n",
    "                cellnext = nxt[m]\n",
    "                p = p + dp(cellnext[0],cellnext[1],k-1)/8\n",
    "            # print('dp({0},{1},{2} = {3})'.format(row,col,k,p))\n",
    "            memo[(row,col,k)] = p\n",
    "            return p\n",
    "\n",
    "        return dp(row,col,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        dir = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2]]\n",
    "        nxtPos = [[[] for _ in range(n)] for _ in range(n)]  # (i,j)的下一跳可能位置\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for d in dir:\n",
    "                    x, y = i + d[0], j + d[1]\n",
    "                    if 0 <= x < n and 0 <= y < n:\n",
    "                        nxtPos[i][j].append((x, y))\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def methods(i, j, k):\n",
    "            \"\"\"位于(i,j)，还能跳k次，有多少种情况留在了棋盘上\"\"\"\n",
    "            nonlocal memo\n",
    "            if k == 1:\n",
    "                return len(nxtPos[i][j])\n",
    "            if (i, j, k) not in memo:\n",
    "                ans = 0\n",
    "                for x, y in nxtPos[i][j]:\n",
    "                    ans += methods(x, y, k - 1)\n",
    "                memo[(i, j, k)] = ans\n",
    "            return memo[(i, j, k)]\n",
    "\n",
    "        return 0.125 ** k * methods(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        steps = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]] \n",
    "        temp = {}\n",
    "\n",
    "        def BFS(k, x, y):\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            if x < 0 or x >= n or y < 0 or y >= n:\n",
    "                return 0\n",
    "            if (k, x, y) in temp.keys():\n",
    "                return temp.get((k, x, y))\n",
    "            else:\n",
    "                count = sum([BFS(k - 1, x + i, y + j) for i, j in steps]) / 8\n",
    "                temp[(k, x, y)] = count\n",
    "                return count\n",
    "        # print(temp)\n",
    "        return BFS(k + 1, row, column)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        movs = [[-2,1],[-2,-1],\n",
    "            [1,-2],[-1,-2],\n",
    "            [2,1],[2,-1],\n",
    "            [1,2],[-1,2],\n",
    "            ]\n",
    "        cnt = [0]\n",
    "        r = {}\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                p = []\n",
    "                for mov in movs:\n",
    "                    mx = i + mov[0]\n",
    "                    my = j + mov[1]\n",
    "                    \n",
    "                    # print(f\"mov {mov} mx {mx} my {my} n-1 {n - 1}\")\n",
    "                    if mx < n and mx > -1 and my < n and my > -1:\n",
    "                        p.append([mx, my])\n",
    "                r[(i, j)] = p\n",
    "        # print(f\"rrr {r}\")\n",
    "        rec = {}\n",
    "        def next(aK, aR, aC) -> int:\n",
    "            key = (aR, aC)\n",
    "            ret = 0\n",
    "            if 0 == aK:\n",
    "                ret = 1.0 if aR < n and aR > -1 and aC < n and aC > -1 else 0\n",
    "            if 1 == aK:\n",
    "                ret = len(r[key])\n",
    "            else:\n",
    "                for p in r[key]:\n",
    "                    rk = (p[0], p[1], aK - 1)\n",
    "                    val = 0\n",
    "                    if rk in rec:\n",
    "                        val = rec[rk]\n",
    "                    else:\n",
    "                        val = next(aK - 1, p[0], p[1])\n",
    "                        rec[rk] = val\n",
    "                    ret += val\n",
    "            return ret\n",
    "        # ret = 0\n",
    "        ret = next(k, row, column)\n",
    "        # print(f\"k {k} rCnt {ret} {len(final)} {final}\")\n",
    "        return ret / 8 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def helper(i,j,k):\n",
    "            if k ==0:\n",
    "                if 0<=i<n and 0<=j<n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                A=[(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(2,-1),(1,-2)]\n",
    "                a = 0\n",
    "                b = 0\n",
    "                for d in A:\n",
    "                    if 0<=d[0]+i<n and 0<=d[1]+j<n:\n",
    "                        a+=helper(d[0]+i,d[1]+j,k-1)/8\n",
    "                return a\n",
    "        return helper(row, column, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        # 动态规划，从起点开始走，每次向八个方向延申\n",
    "        # 所有可能的走法，走出是0，否则是1\n",
    "        @cache\n",
    "        def dfs(ik,r,c):# 未走出/走出\n",
    "            if ik==k:\n",
    "                if r<0 or r>=n or c<0 or c>=n:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            if r<0 or r>=n or c>=n or c<0:\n",
    "                return 0\n",
    "            p=0\n",
    "            for ix,iy in [(-2,-1),(-1,-2),(1,-2),(2,-1),(-2,1),(-1,2),(1,2),(2,1)]:\n",
    "                p+= dfs(ik+1,r+ix,c+iy)\n",
    "            p = p/8 \n",
    "            \n",
    "            return p\n",
    "        \n",
    "        return dfs(0,row,column)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(r, c, counts):\n",
    "            \n",
    "            if r < 0 or r > N - 1 or c < 0 or c > N - 1:\n",
    "                return 0\n",
    "            if counts == K:\n",
    "                return 1\n",
    "\n",
    "            step = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]\n",
    "            res = 0\n",
    "            for i, j in step:\n",
    "                res += dfs(r + i, c + j, counts + 1)\n",
    "            return res / 8\n",
    "\n",
    "        return dfs(r, c, 0)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        memo = {}\n",
    "        def topdown(x, y, rest):\n",
    "            if x >=n or x < 0 or y >= n or y < 0:\n",
    "                return 0\n",
    "            if rest == 0:\n",
    "                return 1\n",
    "            if (x, y, rest) in memo:\n",
    "                return memo[(x, y, rest)]\n",
    "            ans = 0\n",
    "            for dx, dy in [[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                ans += topdown(nx, ny, rest-1)\n",
    "            ans /= 8\n",
    "            memo[(x, y, rest)] = ans\n",
    "            return ans\n",
    "        return topdown(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "       # 就回溯法统计一下不行吗\n",
    "        d = {}\n",
    "        def cal(n,k,x,y):\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            if d.get((k,x,y)) is not None:\n",
    "                return d[(k,x,y)]\n",
    "            xMove = [1,-1,2,-2]\n",
    "            yMove = [1,-1,2,-2]\n",
    "            count = 0\n",
    "            for xm in xMove:\n",
    "                for ym in yMove:\n",
    "                    if abs(xm) + abs(ym) != 3:\n",
    "                        continue\n",
    "                    if isInSide(x+xm,y+ym,n):\n",
    "                        if k == 1:\n",
    "                            count += 1\n",
    "                        else:\n",
    "                            count += cal(n,k-1,x+xm,y+ym)\n",
    "            d[(k,x,y)] = count/8\n",
    "            return count/8\n",
    "\n",
    "        def isInSide(x,y,n):\n",
    "            if x < 0 or y < 0:\n",
    "                return False\n",
    "            if x >= n or y >= n:\n",
    "                return False\n",
    "            return True\n",
    "        return cal(n,k,row,column)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N, K, r, c):\n",
    "            \"\"\"\n",
    "            :type N: int\n",
    "            :type K: int\n",
    "            :type r: int\n",
    "            :type c: int\n",
    "            :rtype: float\n",
    "            \"\"\"\n",
    "            memo = {}\n",
    "            moves = ((-1, -2), (-2, -1),(-2, 1), (-1, 2),(1, -2), (2, -1),(2, 1), (1, 2))\n",
    "            def dfs(K, r, c):\n",
    "                if r < 0 or c < 0 or r >= N or c >= N:\n",
    "                    return 0\n",
    "                if K == 0:\n",
    "                    return 1\n",
    "                if (K, r, c) in memo:\n",
    "                    return memo[(K, r, c)]\n",
    "                p = 0\n",
    "                for move in moves:\n",
    "                    p += dfs(K-1, r+move[0], c+move[1])\n",
    "                p /= 8.0\n",
    "                memo[(K, r, c)] = p\n",
    "                return p\n",
    "            return dfs(K, r, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n",
    "    \n",
    "        @lru_cache(None)\n",
    "        def helper(r, c, k):\n",
    "            if r < 0 or r >= N or c < 0 or c >= N:\n",
    "                return 0\n",
    "            if k <= 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for nx, ny in [(2, -1), (2, 1), (-2, 1), (-2, -1)]:\n",
    "                ans += helper(r + nx, c + ny, k - 1)\n",
    "                ans += helper(r + ny, c + nx, k - 1)\n",
    "            ans /= 8\n",
    "            return ans\n",
    "            \n",
    "        return helper(r, c, K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "       dirs = [[1, 2],[1, -2],[-1, 2],[-1, -2],[2, 1],[2, -1],[-2, 1],[-2, -1]]\n",
    "       @lru_cache(None)\n",
    "       def dfs(i: int, j: int, left: int) -> int:\n",
    "          if i < 0 or i >= n or j < 0 or j >= n:\n",
    "             return 0.0\n",
    "          if left == 0:\n",
    "             return 1.0\n",
    "          res = 0.0\n",
    "          for dx, dy in dirs:\n",
    "             nx = i + dx\n",
    "             ny = j + dy\n",
    "             res += dfs(nx, ny, left - 1)\n",
    "          return res / 8.0\n",
    "       return dfs(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        darr = [[-1, 2], [1, -2], [-1, -2], [1, 2], [-2, 1], [2, -1], [-2, -1], [2, 1]]\n",
    "\n",
    "        @cache\n",
    "        def fun(i, j, step):\n",
    "            if not (i >= 0 and i < n and j >= 0 and j < n):\n",
    "                return 0\n",
    "            if step == k:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            for di in range(8):\n",
    "                ni = i + darr[di][0]\n",
    "                nj = j + darr[di][1]\n",
    "                res += fun(ni, nj, step + 1) / 8\n",
    "            # print([i, j, step], res)\n",
    "            return res\n",
    "\n",
    "        return fun(row, column, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i < 0 or i >= n or j < 0 or j >= n:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            ans += dfs(i - 2, j + 1, k - 1) / 8\n",
    "            ans += dfs(i - 1, j + 2, k - 1) / 8\n",
    "            ans += dfs(i + 1, j + 2, k - 1) / 8\n",
    "            ans += dfs(i + 2, j + 1, k - 1) / 8\n",
    "            ans += dfs(i + 2, j - 1, k - 1) / 8\n",
    "            ans += dfs(i + 1, j - 2, k - 1) / 8\n",
    "            ans += dfs(i - 1, j - 2, k - 1) / 8\n",
    "            ans += dfs(i - 2, j - 1, k - 1) / 8\n",
    "            return ans\n",
    "        return dfs(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        move = [\n",
    "            (-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)\n",
    "        ]\n",
    "\n",
    "        def is_valid(x, y, n):\n",
    "            return 0 <= x < n and 0 <= y < n\n",
    "        \n",
    "        def dfs(x, y, k):\n",
    "            if not is_valid(x, y, n):\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            \n",
    "            if(x, y, k) in memo:\n",
    "                return memo[(x, y, k)]\n",
    "            \n",
    "            prob = 0\n",
    "            for dx, dy in move:\n",
    "                prob += 0.125 * dfs(x + dx, y + dy, k - 1)\n",
    "            \n",
    "            memo[(x, y, k)] = prob\n",
    "            return prob\n",
    "        \n",
    "        memo = {}\n",
    "        return dfs(row, column, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        map=[[1,2],[2,1],[-1,2],[2,-1],[-2,1],[1,-2],[-1,-2],[-2,-1]]\n",
    "        @cache\n",
    "        def dfs(i,j,k):\n",
    "            if not(0<=i<n) or not(0<=j<n):\n",
    "                return 0\n",
    "            if k==0:\n",
    "                return 1\n",
    "            ans=0\n",
    "            for x,y in map:\n",
    "                ans+=dfs(i+x,j+y,k-1)\n",
    "            return ans\n",
    "        return dfs(row,column,k)/8**k\n",
    "                     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        @cache\n",
    "        def f(i: int, j: int, p: int) -> int:       #骑士从(i, j)开始动，动p次，留在棋盘上的次数\n",
    "            if i < 0 or j < 0 or i > n - 1 or j > n - 1:\n",
    "                return 0            #未停留在棋盘上\n",
    "            if p == 0:              #已经动完了，且停留在棋盘上\n",
    "                return 1\n",
    "            #开动\n",
    "            return f(i - 2, j - 1, p - 1) + f(i - 2, j + 1, p - 1) + f(i - 1, j - 2, p - 1) + f(i - 1, j + 2, p - 1) + f(i + 1, j - 2, p - 1) + f(i + 1, j + 2, p - 1) + f(i + 2, j - 1, p - 1) + f(i + 2, j + 1, p - 1)\n",
    "\n",
    "        return f(row, column, k) / pow(8, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        all = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(step, i, j) :\n",
    "            if i < 0 or i >= n or j < 0 or j >= n :\n",
    "                return 0\n",
    "            if step == 0 :\n",
    "                return 1\n",
    "            count = 0\n",
    "            for mi, mj in [(-2, -1),(-1, -2),(2, -1),(1, -2),(-2, 1),(-1, 2),(2, 1),(1, 2)] :\n",
    "                count += dfs(step-1, i+mi, j+mj)\n",
    "            return count\n",
    "        \n",
    "        count = dfs(k, row, column)\n",
    "        return count / (8 ** k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        \"\"\" \"\"\"\n",
    "\n",
    "        moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curr_i, curr_j, steps):\n",
    "            if curr_i < 0 or curr_i >= n or curr_j < 0 or curr_j >= n:\n",
    "                return 0 \n",
    "\n",
    "            if steps == k:\n",
    "                if 0 <= curr_i < n and 0 <= curr_j < n:\n",
    "                    return 1 \n",
    "                else:\n",
    "                    return 0 \n",
    "\n",
    "            ans = 0 \n",
    "            for dx, dy in moves:\n",
    "                new_i, new_j = curr_i+dx, curr_j+dy \n",
    "                if 0 <= new_i < n and 0 <= new_j < n:\n",
    "                    ans += dfs(new_i, new_j, steps+1)\n",
    "            return ans \n",
    "\n",
    "        # print(dfs(row, column, 0))\n",
    "\n",
    "        return dfs(row, column, 0) / (8 ** k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        \"\"\" \"\"\"\n",
    "\n",
    "        moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]\n",
    "        # vis = set()\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curr_i, curr_j, steps):\n",
    "            if curr_i < 0 or curr_i >= n or curr_j < 0 or curr_j >= n:\n",
    "                return 0 \n",
    "\n",
    "            if steps == k:\n",
    "                if 0 <= curr_i < n and 0 <= curr_j < n:\n",
    "                    return 1 \n",
    "                else:\n",
    "                    return 0 \n",
    "\n",
    "            ans = 0 \n",
    "            for dx, dy in moves:\n",
    "                new_i, new_j = curr_i+dx, curr_j+dy \n",
    "                if 0 <= new_i < n and 0 <= new_j < n:\n",
    "                    ans += dfs(new_i, new_j, steps+1)\n",
    "            return ans \n",
    "\n",
    "        print(dfs(row, column, 0))\n",
    "\n",
    "        return dfs(row, column, 0) / (8 ** k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        return 1 if not k else sum(self.knightProbability(n, k - 1, nr, nc) / 8 for dir in DIRS if 0<=(nr:=row + dir[0])<n and 0<=(nc:=column + dir[1])<n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        visited = [[0]*n for _ in range(n)]\n",
    "        directions = [[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]\n",
    "        @functools.cache\n",
    "        def dfs(i,j,cnt):\n",
    "            if cnt == k:\n",
    "                if 0<=i<n and 0<=j<n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            res = 0\n",
    "            for direction in directions:\n",
    "                newi = i + direction[0]\n",
    "                newj = j + direction[1]\n",
    "                if (0<=newi<n and 0<=newj<n and visited[newi][newj]==0) :\n",
    "                    res += dfs(newi,newj,cnt+1)\n",
    "            return  res\n",
    "\n",
    "        ans = dfs(row,column,0)/8**k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "\n",
    "        acs = [(1, 2), (2, 1), (1, -2), (-2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1)]\n",
    "        @ cache\n",
    "        def dfs(cur_pos, step):\n",
    "            if cur_pos[0] < 0 or cur_pos[0] > n - 1 or cur_pos[1] < 0 or cur_pos[1] > n - 1:\n",
    "                return 0\n",
    "            if step == k:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for ac in acs:\n",
    "                ans += dfs((cur_pos[0] + ac[0], cur_pos[1] + ac[1]), step + 1) / 8\n",
    "            return ans\n",
    "\n",
    "        return dfs((row, column), 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        \n",
    "        #dp = [[[0.0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)]\n",
    "        dp = [[[0.0]*n  for _ in range(n)] for _ in range(k + 1)]\n",
    "\n",
    "       \n",
    "\n",
    "        \n",
    "        #dp[:][:][0]=1\n",
    "        print (dp)\n",
    "        def getv(x,y,rest):\n",
    "            if x>=n or x<0 or y>=n or y<0:\n",
    "                return 0\n",
    "            else:\n",
    "                return dp[rest][x][y]\n",
    "        for r in range(k+1):\n",
    "            for a in range(n):\n",
    "                for b in range(n):\n",
    "               \n",
    "                    if r==0:\n",
    "                        dp[r][a][b]=1\n",
    "                    else:\n",
    "                        dp[r][a][b]=getv(a-2,b+1,r-1)+getv(a-1,b-2,r-1)+getv(a+1,b-2,r-1)+getv(a+2,b-1,r-1)+getv(a-2,b-1,r-1)+getv(a-1,b+2,r-1)+getv(a+1,b+2,r-1)+getv(a+2,b+1,r-1)\n",
    "             \n",
    "\n",
    "\n",
    "            \n",
    "        if k==0:\n",
    "            return 1    \n",
    "        print(dp)   \n",
    "        print(getv(row+1,column+2,k-1)) \n",
    "        print(getv(row+2,column+1,k-1)) \n",
    "        step=dp[k][row][column]\n",
    "        print(step)\n",
    "        ratio=step/(8**k)\n",
    "        return ratio\n",
    "\n",
    "          \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        \n",
    "        dp = [[[0.0 for _ in range(n)] for _ in range(n)] for _ in range(k + 1)]\n",
    "       \n",
    "\n",
    "        \n",
    "        #dp[:][:][0]=1\n",
    "        print (dp)\n",
    "        def getv(x,y,rest):\n",
    "            if x>=n or x<0 or y>=n or y<0:\n",
    "                return 0\n",
    "            else:\n",
    "                return dp[rest][x][y]\n",
    "        for r in range(k+1):\n",
    "            for a in range(n):\n",
    "                for b in range(n):\n",
    "               \n",
    "                    if r==0:\n",
    "                        dp[r][a][b]=1\n",
    "                    else:\n",
    "                        dp[r][a][b]=getv(a-2,b+1,r-1)+getv(a-1,b-2,r-1)+getv(a+1,b-2,r-1)+getv(a+2,b-1,r-1)+getv(a-2,b-1,r-1)+getv(a-1,b+2,r-1)+getv(a+1,b+2,r-1)+getv(a+2,b+1,r-1)\n",
    "             \n",
    "\n",
    "\n",
    "            \n",
    "        if k==0:\n",
    "            return 1    \n",
    "        print(dp)   \n",
    "        print(getv(row+1,column+2,k-1)) \n",
    "        print(getv(row+2,column+1,k-1)) \n",
    "        step=dp[k][row][column]\n",
    "        print(step)\n",
    "        ratio=step/(8**k)\n",
    "        return ratio\n",
    "\n",
    "          \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        # 特判\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        # dp[row][col][step][in,all]\n",
    "        dp = [[[[0,0] for _ in range(k)] for _ in range(n)] for _ in range(n)]\n",
    "        direct = [(-2,-1),(-2,1),(-1,2),(-1,-2),(2,1),(2,-1),(1,2),(1,-2)]\n",
    "\n",
    "        def inBoard(r,c):\n",
    "            if r < 0 or r >= n or c < 0 or c >= n:\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                dp[r][c][0][1] = 8\n",
    "                for dr,dc in direct:\n",
    "                    rr,cc = r+dr,c+dc\n",
    "                    dp[r][c][0][0] += inBoard(rr,cc)\n",
    "        for i in range(1,k):\n",
    "            for r in range(n):\n",
    "                for c in range(n):\n",
    "                    for dr,dc in direct:\n",
    "                        rr,cc = r+dr,c+dc\n",
    "                        if inBoard(rr,cc):\n",
    "                            dp[r][c][i][0] += dp[rr][cc][i-1][0]\n",
    "                    dp[r][c][i][1] = dp[r][c][i-1][1]*8\n",
    "        return dp[row][column][-1][0]/dp[row][column][-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n",
    "        nxt = [\n",
    "            (row - 1, column - 2),\n",
    "            (row - 1, column + 2),\n",
    "            (row + 1, column - 2),\n",
    "            (row + 1, column + 2),\n",
    "            (row - 2, column - 1),\n",
    "            (row - 2, column + 1),\n",
    "            (row + 2, column - 1),\n",
    "            (row + 2, column + 1),\n",
    "        ]\n",
    "        res = 0\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        for x, y in nxt:\n",
    "            if 0 <= x < n and 0 <= y < n:\n",
    "                res += (1 / 8) * self.knightProbability(n, k - 1, x, y)\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
